package leetcode.editor.cn.q1_300.q250;
//序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方
//式重构得到原数据。 
//
// 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串
//反序列化为原始的树结构。 
//
// 提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的
//方法解决这个问题。 
//
// 
//
// 示例 1： 
// 
// 
//输入：root = [1,2,3,null,null,4,5]
//输出：[1,2,3,null,null,4,5]
// 
//
// 示例 2： 
//
// 
//输入：root = []
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：root = [1]
//输出：[1]
// 
//
// 示例 4： 
//
// 
//输入：root = [1,2]
//输出：[1,2]
// 
//
// 
//
// 提示： 
//
// 
// 树中结点数在范围 [0, 10⁴] 内 
// -1000 <= Node.val <= 1000 
// 
//
// 👍 1128 👎 0

import leetcode.editor.cn.util.tree.btree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.Collectors;

/**
 * 很无聊的一题，随便一种遍历保存为字符串就可以，但是还需要还原，所以层序遍历最简单
 * 执行耗时:23 ms,击败了27.87% 的Java用户
 * 内存消耗:43.1 MB,击败了84.41% 的Java用户
 */
public class Q297_SerializeAndDeserializeBinaryTree {
    //leetcode submit region begin(Prohibit modification and deletion)

    public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            Queue<TreeNode> q1 = new LinkedList<>();
            ArrayList<Integer> serList = new ArrayList<>();
            q1.add(root);
            while (!q1.isEmpty()) {
                TreeNode node = q1.poll();
                if (node == null) {
                    serList.add(null);
                    continue;
                }
                serList.add(node.val);
                q1.add(node.left);
                q1.add(node.right);
            }
            return serList.stream().map(item -> item == null ? "-" : String.valueOf(item)).collect(Collectors.joining(","));
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            String[] arr = data.split(",");
            if (arr[0].equals("-")) {
                return null;
            }

            TreeNode node = new TreeNode(Integer.parseInt(arr[0]));

            Queue<TreeNode> q = new LinkedList<>();
            q.add(node);

            int i = 0;
            while (!q.isEmpty()) {
                TreeNode poll = q.poll();
                if (poll == null) {
                    continue;
                }
                poll.left = arr[++i].equals("-") ? null : new TreeNode(Integer.parseInt(arr[i]));
                poll.right = arr[++i].equals("-") ? null : new TreeNode(Integer.parseInt(arr[i]));
                q.add(poll.left);
                q.add(poll.right);
            }

            return node;
        }
    }

    // Your Codec object will be instantiated and called as such:
    // Codec ser = new Codec();
    // Codec deser = new Codec();
    // TreeNode ans = deser.deserialize(ser.serialize(root));
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);

        node1.left = node2;
        node1.right = node3;

        node3.left = node4;
        node3.right = node5;

        Codec ser = new Q297_SerializeAndDeserializeBinaryTree().new Codec();
        Codec deser = new Q297_SerializeAndDeserializeBinaryTree().new Codec();
        // TO TEST
        TreeNode ans = deser.deserialize(ser.serialize(node1));
        deser.deserialize(ser.serialize(null));
    }
}